package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*
题型：二叉树的层级遍历
 637. 二叉树的层平均值
 https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/
 https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_637-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%B9%B3%E5%9D%87%E5%80%BC

 示例 1：
 输入：root = [3,9,20,null,null,15,7]
 输出：[3.00000,14.50000,11.00000]
 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
 因此返回 [3, 14.5, 11] 。

 示例 2:
 输入：root = [3,9,20,15,7]
 输出：[3.00000,14.50000,11.00000]
 
 示例 3:
 输入：root = [2147483647,2147483647,2147483647]
 输出：[2147483647.0,2147483647.0]
 */
class leetcode_637 {
    @Test
    fun test_1() {
        val n3 = TreeNode(3)
        val n9 = TreeNode(9)
        val n20 = TreeNode(20)
        val n15 = TreeNode(15)
        val n7 = TreeNode(7)
        n3.left = n9
        n3.right = n20
        n20.left = n15
        n20.right = n7
        val actual = averageOfLevels(n3)
        val expect = doubleArrayOf(3.00000, 14.50000, 11.00000)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        val n3 = TreeNode(3)
        val n9 = TreeNode(9)
        val n20 = TreeNode(20)
        val n15 = TreeNode(15)
        val n7 = TreeNode(7)
        n3.left = n9
        n3.right = n20
        n9.left = n15
        n9.right = n7
        val actual = averageOfLevels(n3)
        val expect = doubleArrayOf(3.00000, 14.50000, 11.00000)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_3() {
//        输入：root = [2147483647,2147483647,2147483647]
//        输出：[2147483647.0,2147483647.0]

        val root = TreeNode(2147483647)
        val left = TreeNode(2147483647)
        val right = TreeNode(2147483647)
        root.left = left
        root.right = right
        val actual = averageOfLevels(root)
        val expect = doubleArrayOf(2147483647.0, 2147483647.0)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    private fun averageOfLevels(root: TreeNode?): DoubleArray {
        // 层级遍历，然后求每层的平均值
        // S - N
        // T - N
        if (null == root) {
            // TODO：
            return DoubleArray(0)
        }
        val list: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)

        while (!queue.isEmpty()) {
            var size: Int = queue.size
            val row: ArrayList<Int> = ArrayList<Int>()
            while (size-- > 0) {
                val node: TreeNode = queue.poll()
                row.add(node.`val`)
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
            list.add(row)
        }
        val result: DoubleArray = DoubleArray(list.size)
        for (i in 0..list.size - 1) {
            val size: Int = list[i].size
            // TODO: use Double, not int
            var sum: Double = 0.0
            for (n in list[i]) {
                sum += n
            }
            result[i] = sum / size
        }
        return result
    }

    fun averageOfLevels2(root: TreeNode?): DoubleArray {
        if (root == null) {
            // TODO：
            return doubleArrayOf()
        }
        // 1 初始化队列
        val queue: LinkedList<TreeNode> = LinkedList()
        queue.offer(root)
        // TODO：
        val result: ArrayList<Double> = ArrayList()

        // 2 遍历层
        while (!queue.isEmpty()) {
            var size = queue.size
            val n = size
            // TODO：
            var sum: Double = 0.0

            // 3 层级遍历
            while (size-- > 0) {
                // 退出队列?
                val node = queue.poll()
                sum = sum + node.`val`
                node.left?.let {
                    queue.offer(it)
                }
                node.right?.let {
                    queue.offer(it)
                }
            }
            val ave = sum / n
            result.add(ave)
        }
        // TODO：
        return result.toDoubleArray()
    }
}